package a11_单调栈;

import java.util.Stack;

/**
 * <p>
 * a01_每日温度
 * </p>
 *
 * @author flyduck
 * @since 2025/3/6
 */
public class a01_每日温度 {

    public static void main(String[] args) {
        a01_每日温度 test = new a01_每日温度();
        test.dailyTemperatures(new int[]{73,74,75,71,69,69,72,76,73});
    }

    //73,74,75,71,69,69,72,76,73
    //单调栈：存放的之前遍历过的元素的索引
    //如果发现当前元素比之前遍历过的元素大
    //st                          st.top     T[i]       result
    //0(73)                                  0(73)      []
    //0(73)1(74)                  0(73)   <  1(74)      [1-0=1],0已经记录了就可以弹出0(73)了
    //1(74)2(75)                  1(74)   <  2(75)      [1-0=1,2-1=1],1已经记录了就可以弹出1(74)了
    //2(75)3(71)                  2(75)   >  3(71)
    //2(75)3(71)4(69)             3(71)   >  4(69)
    //2(75)3(71)4(69)5(69)        4(69)   =  5(69)
    //2(75)3(71)4(69)5(69)6(72)   5(69)   <  6(72)      [1-0=1,2-1=1,,6-3=3,6-4=2,6-5=1],5已经记录了就可以弹出5(69)了,4已经记录了就可以弹出4(69)了,3已经记录了就可以弹出3(71)了
    //2(75)6(72)                  6(72)   <  7(76)      [1-0=1,2-1=1,7-2=5,6-3=3,6-4=2,6-5=1,7-6=1],6已经记录了就可以弹出6(72)了,2已经记录了就可以弹出2(75)了
    //7(76)8(73)                  7(76)   >  8(73)

    //总结
    //栈里面存放的是 还没有找到比当前温度高的索引
    //为啥栈顶存放的最小的：
    //这样想：假设栈里面有3个元素比当天的温度低，但栈顶的不是这3个元素，那么需要将所有都遍历一遍。如果从栈底到栈顶从大到小，那么我们从栈顶一个一个比较就行了
    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];

        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        for (int i = 1; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
                Integer pop = stack.pop();
                result[pop] = i - pop;
            }
            stack.push(i);
        }

        return result;
    }
}
